#include "myTree.h"
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
static TreeNode nullNode('@', nullptr, nullptr, Link, Link);

// TreeNode构造函数
TreeNode::TreeNode(char val, TreeNode* left, TreeNode* right, NodeTag lt, NodeTag rt) 
    : data(val), leftChild(left), rightChild(right), lTag(lt), rTag(rt) {}

// TreeNode析构函数
TreeNode::~TreeNode() {}

void TreeNode::printNode(){
    cout << this->data;
}

// MyTree构造函数 - 初始化空树
MyTree::MyTree() : root(nullptr), isThread(false) {}

TreeNode* MyTree::constructFromPreorder(const char preOrder[], int& idx) {
    if (preOrder[idx] == '@') {
        idx++;  // 跳过 '@'
        return nullptr;
    }
    // 创建当前节点
    TreeNode* node = new TreeNode(preOrder[idx++],nullptr, nullptr, Link, Link);
    // 递归构造左子树和右子树
    node->leftChild = constructFromPreorder(preOrder, idx);
    node->rightChild = constructFromPreorder(preOrder, idx);
    return node;
}

// MyTree构造函数 - 用字符串初始化树
MyTree::MyTree(const char preOrder[]) : root(nullptr), isThread(false) {
    int index = 0;  // 初始化索引
    root = constructFromPreorder(preOrder, index);
}

TreeNode* MyTree::copyTree(const TreeNode* node) {
    if (!node) return nullptr;
    // 复制当前节点
    TreeNode* newNode = new TreeNode(node->data, nullptr, nullptr, node->lTag, node->rTag);
    // 递归复制左右子树
    newNode->leftChild = copyTree(node->leftChild);
    newNode->rightChild = copyTree(node->rightChild);
    return newNode;
}

// 拷贝构造函数
MyTree::MyTree(const MyTree& other) : root(nullptr), isThread(other.isThread) {
    root = copyTree(other.root);
}

void MyTree::deleteTree(TreeNode* node) {
    if (!node) return;
    // 只对普通二叉树进行递归删除，忽略线索指针
    if (node->lTag == Link) {
        deleteTree(node->leftChild);  // 删除左子树
    }
    if (node->rTag == Link) {
        deleteTree(node->rightChild);  // 删除右子树
    }
    // 删除当前节点
    delete node;
}


// 析构函数
MyTree::~MyTree() {
    deleteTree(root);
    root = nullptr;
}

void MyTree::preOrderTraverse() {
    if (root == nullptr) return;
    stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        // 访问节点
        node->printNode();
        // 先将右子节点压入栈
        if (node->rightChild) {
            nodeStack.push(node->rightChild);
        }
        // 再将左子节点压入栈
        if (node->leftChild) {
            nodeStack.push(node->leftChild);
        }
    }
}

void MyTree::inOrderTraverse() {
    if (!root) return; // 如果树为空，则直接返回
    if (isThread) {
        // 如果是线索二叉树，使用线索化的递归遍历
        inOrderThreadedTraverse(root);
    } else {
        // 如果是普通二叉树，使用普通的递归中序遍历
        inOrderNormalTraverse(root);
    }
}

// 递归中序遍历普通二叉树
void MyTree::inOrderNormalTraverse(TreeNode* node) {
    if (node == nullptr) return;
    // 递归遍历左子树
    inOrderNormalTraverse(node->leftChild);
    // 访问当前节点
    node->printNode();
    // 递归遍历右子树
    inOrderNormalTraverse(node->rightChild);
}

// 递归中序遍历线索二叉树
void MyTree::inOrderThreadedTraverse(TreeNode* node) {
    TreeNode* p = node;  // 从根结点开始遍历
    while (p != nullptr) {
        // 寻找最左的结点
        while (p->lTag == Link) {
            p = p->leftChild;
        }
        // 打印当前结点
        p->printNode();
        // 如果当前结点的右子树是线索，直接跳到后继结点
        while (p->rTag == Thread && p->rightChild != nullptr) {
            p = p->rightChild;
            p->printNode();
        }
        // 跳到右子树
        p = p->rightChild;
    }
}

void MyTree::postOrderTraverse() {
    if (root == nullptr) return;
    stack<TreeNode*> nodeStack, outputStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        outputStack.push(node);
        // 先压左子节点
        if (node->leftChild) {
            nodeStack.push(node->leftChild);
        }
        // 再压右子节点
        if (node->rightChild) {
            nodeStack.push(node->rightChild);
        }
    }
    // 输出栈中节点的访问结果
    while (!outputStack.empty()) {
        TreeNode* node = outputStack.top();
        outputStack.pop();
        node->printNode();
    }
}

// 普通二叉树和线索二叉树节点查找
TreeNode& MyTree::locateNode(const char& v) {
    if (isThread) {
        // 如果是线索二叉树，使用线索化的查找方法
        return locateNodeInThreadedTree(v);
    } else {
        // 如果是普通二叉树，使用递归查找
        return locateNodeInNormalTree(root, v);
    }
}

// 在普通二叉树中查找节点
TreeNode& MyTree::locateNodeInNormalTree(TreeNode* node, const char& v) {
    if (node == nullptr) {
        // 如果节点为空，返回一个虚拟的空节点
        throw std::runtime_error("Node not found");
    }
    if (node->data == v) {
        return *node;  // 找到节点，返回该节点
    }
    // 递归查找左子树和右子树
    TreeNode* leftResult = nullptr;
    try {
        leftResult = &locateNodeInNormalTree(node->leftChild, v);
    } catch (...) {
        // 处理未找到左子树节点的异常
    }
    if (leftResult != nullptr) {
        return *leftResult;
    }
    TreeNode* rightResult = nullptr;
    try {
        rightResult = &locateNodeInNormalTree(node->rightChild, v);
    } catch (...) {
        // 处理未找到右子树节点的异常
    }
    if (rightResult != nullptr) {
        return *rightResult;
    }
    // 如果都未找到，抛出异常
    throw std::runtime_error("Node not found");
}

// 在线索二叉树中查找节点
TreeNode& MyTree::locateNodeInThreadedTree(const char& v) {
    TreeNode* p = root;
    while (p != nullptr) {
        // 先通过左指针线索进行遍历
        while (p->lTag == Link) {
            p = p->leftChild;
        }
        // 如果当前节点是目标节点，返回该节点
        if (p->data == v) {
            return *p;
        }
        // 如果右子树是线索，直接跳到后继节点
        while (p->rTag == Thread && p->rightChild != nullptr) {
            p = p->rightChild;
            if (p->data == v) {
                return *p;  // 找到目标节点，返回该节点
            }
        }
        // 否则，进入右子树
        p = p->rightChild;
    }
    // 如果未找到目标节点，抛出异常
    throw std::runtime_error("Node not found");
}


int MyTree::countLeaf() {
    if (root == nullptr) return 0;
    int leafCount = 0;
    stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top();
        nodeStack.pop();
        // 如果是叶子节点，则计数加1
        if (node->leftChild == nullptr && node->rightChild == nullptr) {
            leafCount++;
        }
        // 压入右子树和左子树（如果有的话）
        if (node->rightChild) {
            nodeStack.push(node->rightChild);
        }
        if (node->leftChild) {
            nodeStack.push(node->leftChild);
        }
    }
    return leafCount;
}

int MyTree::countHeight() {
    if (root == nullptr) return 0;
    stack<pair<TreeNode*, int>> nodeStack;  // 存储节点和当前深度
    nodeStack.push({root, 1});
    int maxHeight = 0;
    while (!nodeStack.empty()) {
        TreeNode* node = nodeStack.top().first;
        int depth = nodeStack.top().second;
        nodeStack.pop();
        // 更新最大深度
        maxHeight = max(maxHeight, depth);
        // 压入右子树和左子树（如果有的话）
        if (node->rightChild) {
            nodeStack.push({node->rightChild, depth + 1});
        }
        if (node->leftChild) {
            nodeStack.push({node->leftChild, depth + 1});
        }
    }
    return maxHeight;
}

bool MyTree::isThreadedTree() {
    return isThread;  // 所有节点都符合线索二叉树的要求
}

bool MyTree::inOrderThreading() {
    if (!root) {
        // 若树为空，直接返回，设为线索二叉树并返回 true
        isThread = true;
        return true;
    }
    TreeNode* pre = nullptr; // 记录前驱节点
    inOrderThreadingHelper(root, pre); // 调用辅助函数进行线索化
    // 处理中序遍历的最后一个节点，使其右指针指向根节点
    if (pre) {
        pre->rTag = Thread;
        pre->rightChild = nullptr; // 设置最后一个节点的后继为空
    }
    isThread = true; // 标记为线索二叉树
    return true;
}

void MyTree::inOrderThreadingHelper(TreeNode* node, TreeNode*& pre) {
    if (!node) return;
    // 递归线索化左子树
    inOrderThreadingHelper(node->leftChild, pre);
    // 当前节点的左线索设置
    if (!node->leftChild) {
        node->lTag = Thread;
        node->leftChild = pre;
    }
    // 前驱节点的右线索设置
    if (pre && !pre->rightChild) {
        pre->rTag = Thread;
        pre->rightChild = node;
    }
    // 更新前驱指针为当前节点
    pre = node;
    // 递归线索化右子树
    inOrderThreadingHelper(node->rightChild, pre);
}

TreeNode& MyTree::preNode(const TreeNode& node) {
    if (node.lTag == Thread) {
        // 如果左指针是线索，则返回前驱节点
        return *node.leftChild;
    } else {
        // 否则，返回左子树的最右节点
        TreeNode* curr = node.leftChild;
        while (curr && curr->rTag == Link) {
            curr = curr->rightChild;
        }
        return *curr;
    }
}

TreeNode& MyTree::nextNode(const TreeNode& node) {
    if (node.rTag == Thread) {
        // 如果右指针是线索，则返回后继节点
        return *node.rightChild;
    } else {
        // 否则，返回右子树的最左节点
        TreeNode* curr = node.rightChild;
        while (curr && curr->lTag == Link) {
            curr = curr->leftChild;
        }
        return *curr;
    }
}

void HuffmanTree::generateCodes(HuffmanNode* node, string code) {
    if (!node->left && !node->right) {  // 叶子节点
        codes[node->value] = code;
        return;
    }
    if (node->left) generateCodes(node->left, code + "0");
    if (node->right) generateCodes(node->right, code + "1");
}

HuffmanTree::HuffmanTree(const int& n, const int values[]) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNode> pq;
    // 创建叶子节点并插入优先队列
    for (int i = 0; i < n; ++i) {
        pq.push(new HuffmanNode(values[i]));
    }
    // 构建霍夫曼树
    while (pq.size() > 1) {
        // 取出权重最小的两个节点
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        // 创建一个新的内部节点，权重为左右子节点权重之和
         HuffmanNode* parent = new HuffmanNode(left->value + right->value);
        parent->left = left;
        parent->right = right;
        // 将新节点插入优先队列
        pq.push(parent);
        }
    // 最终队列中剩下的唯一节点就是树的根
    root = pq.top();
    // 生成霍夫曼编码
    generateCodes(root, "");
}

// 析构函数，递归删除霍夫曼树
HuffmanTree::~HuffmanTree() {
    deleteTree(root);
}

void HuffmanTree::deleteTree(HuffmanNode* node) {
    if (node) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

    // 输出霍夫曼编码
void HuffmanTree::printHuffmanCodes() {
   // 将节点按权重从大到小排序后输出
    vector<pair<int, string>> sortedCodes(codes.begin(), codes.end());
    sort(sortedCodes.rbegin(), sortedCodes.rend());
    for (const auto& code : sortedCodes) {
    cout << code.first << ":" << code.second << endl;
    }
}